package com.gxc.object;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 676. 实现一个魔法字典

 * 设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。
 * 如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。
 *
 * 实现 MagicDictionary 类：
 *
 * MagicDictionary() 初始化对象
 * void buildDict(String[] dictionary) 使用字符串数组 dictionary 设定该数据结构，
 * dictionary 中的字符串互不相同
 * bool search(String searchWord) 给定一个字符串 searchWord ，
 * 判定能否只将字符串中 一个 字母换成另一个字母，使得所形成的新字符串能够与字典中的任一字符串匹配。如果可以，返回 true ；否则，返回 false 。
 */
public class MagicDictionary {

    public static void main(String[] args) {
        MagicDictionary magicDictionary = new MagicDictionary();
        magicDictionary.buildDict(new String[]{"hello","leetcode"});
        System.out.println(magicDictionary.search("hhllo"));
    }

    public Map<Integer, List<String>> map = new HashMap<>();

    public MagicDictionary() {

    }

    public void buildDict(String[] dictionary) {
        for (int i = 0; i < dictionary.length; i++) {
            String s = dictionary[i];
            List<String> list = map.getOrDefault(s.length(), new ArrayList<>());
            list.add(s);
            map.put(s.length(), list);
        }
    }

    public boolean search(String searchWord) {
        int length = searchWord.length();
        List<String> list = map.get(length);
        if (list == null) return false;

        for (String str : list) {
            int diff = 0;
            for (int i = 0; i < length; i++) {
                if (searchWord.charAt(i) == str.charAt(i)) {

                } else {
                    diff++;
                }
                if (diff > 1) break;
            }
            if (diff == 1) return true;
        }
        return false;
    }

    class MagicDictionary1 {
        private String[] words;

        public MagicDictionary1() {

        }

        public void buildDict(String[] dictionary) {
            words = dictionary;
        }

        public boolean search(String searchWord) {
            for (String word : words) {
                if (word.length() != searchWord.length()) {
                    continue;
                }

                int diff = 0;
                for (int i = 0; i < word.length(); ++i) {
                    if (word.charAt(i) != searchWord.charAt(i)) {
                        ++diff;
                        if (diff > 1) {
                            break;
                        }
                    }
                }
                if (diff == 1) {
                    return true;
                }
            }
            return false;
        }
    }

    class MagicDictionary2 {
        Trie root;

        public MagicDictionary2() {
            root = new Trie();
        }

        public void buildDict(String[] dictionary) {
            for (String word : dictionary) {
                Trie cur = root;
                for (int i = 0; i < word.length(); ++i) {
                    char ch = word.charAt(i);
                    int idx = ch - 'a';
                    if (cur.child[idx] == null) {
                        cur.child[idx] = new Trie();
                    }
                    cur = cur.child[idx];
                }
                cur.isFinished = true;
            }
        }

        public boolean search(String searchWord) {
            return dfs(searchWord, root, 0, false);
        }

        private boolean dfs(String searchWord, Trie node, int pos, boolean modified) {
            if (pos == searchWord.length()) {
                return modified && node.isFinished;
            }
            int idx = searchWord.charAt(pos) - 'a';
            if (node.child[idx] != null) {
                if (dfs(searchWord, node.child[idx], pos + 1, modified)) {
                    return true;
                }
            }
            if (!modified) {
                for (int i = 0; i < 26; ++i) {
                    if (i != idx && node.child[i] != null) {
                        if (dfs(searchWord, node.child[i], pos + 1, true)) {
                            return true;
                        }
                    }
                }
            }
            return false;
        }
    }

    class Trie {
        boolean isFinished;
        //用数组结构代替链表，空间换时间（链表查找是否存在需要循环）
        Trie[] child;

        public Trie() {
            isFinished = false;
            child = new Trie[26];
        }
    }


}
